The present invention relates to a method and apparatus for allocating a bandwidth of a video signal having variable bit rates; and, more particularly, to a method and apparatus for determining a bandwidth of a video signal based on the fractal surface areas thereof.
With the recent availability of large data sets of actual VBR(variable bit rate) video traffic measurements, the inherent features of the VBR video traffic, i.e., the features which are independent of scene and codec, have become one of the major topics in the traffic engineering for high-speed networks. The idea of utilizing the inherent features of the VBR video traffic may make it possible to move away from the models that are highly dependent on the scene and/or codec specifics toward a more universal description of the VBR video traffic.
The transport of VBR video images from such applications as video conference, video telephone, and full motion broadcast and studio quality video is expected to become a major traffic component of the networks. In order for these networks to meet the stringent performance criteria required for the VBR services and to provide efficient multimedia communications, the use of the ATM(asynchronous transfer mode) technique has been proposed.
In the ATM technique, a bandwidth is allocated to the VBR video traffic based on the inherent features characterizing of the VBR video traffic. One of the inherent features is a Hurst parameter representing the characteristics of the VBR video traffic(see, e.g., J. Beran et al., xe2x80x9cLong-Range Dependence in Variable-Bit-Rate Video Trafficxe2x80x9d, IEEE Trans. on Commun., Vol. 43, No. 2/3/4, pp. 1566-1579, 1995), wherein the Hurst parameter is calculated by using a rescaled adjusted range statistics or, for short, R/S statistics.
Assuming observations or sequences Xk""s of video data having N frames, N being a positive integer and k being an integer ranging from 1 to N and Xk representing the number of encoded bits for a kth frame of the video signal, the sample mean and the sample variance of the sequences Xk""s are XM(N) and S2(N), respectively, the R/S statistics of the sequences Xk""s may be defined as:                                           R            ⁡                          (              N              )                                            S            ⁡                          (              N              )                                      =                                                                              [                                                            max                      ⁡                                              (                                                  0                          ,                                                      W                            1                                                    ,                                                      W                            2                                                    ,                          ⋯                          ⁢                                                      xe2x80x83                                                    ,                                                      W                            N                                                                          )                                                              -                                                                                                                                            min                    ⁢                                          (                                              0                        ,                                                  W                          1                                                ,                                                  W                          2                                                ,                        ⋯                        ⁢                                                  xe2x80x83                                                ,                                                  W                          N                                                                    )                                                        ]                                                              S                                    Eq        .                  xe2x80x83                ⁢                  (          1          )                    
wherein, Wk=(X1+X2+xc2x7xc2x7xc2x7+Xk)xe2x88x92kxc2x7Xm(N).
And, the expectation of R(N)/S(N) may be given by:                                           E            ⁡                          [                                                R                  ⁡                                      (                    N                    )                                                                    S                  ⁡                                      (                    N                    )                                                              ]                                ≈                      C            ·                          N              H                                      ,                  xe2x80x83                ⁢                              as            ⁢                          xe2x80x83                        ⁢            N                    →          ∞                                    Eq        .                  xe2x80x83                ⁢                  (          2          )                    
wherein C is a constant and H is a Hurst parameter. The Hurst parameter is calculated based on Eqs.(1) and (2).
In practice, R/S analysis is based on a heuristic graphical approach. Formally, given a sample of N observations Xk""s, the entire samples are subdivided into K non-overlapping blocks, K being a positive integer smaller than N, and the rescaled adjusted range R(ti,d)/S(ti,d) for each of new starting points is computed, wherein the new starting points are t1=1, t2=(N/K)+1, t3=(2N/K)+1, xc2x7xc2x7xc2x7, tK={(Kxe2x88x921)xc2x7N/K}+1 and satisfy (tKxe2x88x921)+dxe2x89xa6N. Here, R(ti, d) is defined as in Eq. (1) with Wk replaced by Wti+kxe2x88x92Wti and S2(ti, d) is the sample variance of Xti+1, Xti+2, xc2x7xc2x7xc2x7, Xti+d. Thus, for a given value of d, as many as K samples of R/S are obtained when d is small and as few as one sample is obtained when d is close to the total sample size N.
Next, logarithmically spaced values of d, starting with d≈10, are taken. Plotting log{R(ti,d)/S(ti,d)} versus log(d) results in a rescaled adjusted range plot. When the Hurst parameter H is defined, a typical rescaled adjusted range plot starts with a transient zone representing the short range dependence in the sample, but will eventually settle down and fluctuate along a straight street of slope H. A graphical R/S analysis is used to determine whether such an asymptotic behavior is supported by the data; and if it is affirmative, the asymptotic value of the Hurst exponent H is estimated usually by simple least square fit, wherein the value of the Hurst exponent H asymptotically approaches to the value of the street""s slope.
Thereafter, the VBR video traffic is classified into roughly 3 categories, i.e., low-, medium-, and high-activity, based on the values of the corresponding empirical Hurst parameter. If the Hurst parameter lies between 0.5 and 0.75, the VBR video traffic corresponds to the low-activity category; if the Hurst parameter greater than 0.75 and smaller than 0.9, the VBR video traffic belongs to the medium-activity category; and if the Hurst parameter gets close to 1, the VBR video traffic falls in the high-activity category. Based on the classification, the VBR video traffic is allocated with a corresponding bandwidth and is transmitted to the ATM network by using the allocated bandwidth.
In the conventional R/S analysis scheme described above, the Hurst parameter is calculated by using the sample mean and the sample variance. Furthermore, the multiplication and divisional computations exalt a lengthy computation time. Thus, there has existed a need to develop a simpler scheme to compute the Hurst parameter.
It is, therefore, a primary object of the invention to provide a more efficient method and apparatus for determining a hurst parameter of a video signal having variable bit rates by using the fractal surface areas thereof.
In accordance with one aspect of the present invention, there is provided a method for allocating a bandwidth to bit streams of a video signal having variable bit rates, wherein the bit streams are transmitted to an ATM(asynchronous transfer mode) network, comprising the steps of: (a) encoding the video signal to thereby generate the bit streams of the encoded video signal; (b) generating a bit function B(i) of the bit streams, wherein the bit function represents the amount of bits per predetermined ith unit in the bit streams, i being an index of the predetermined unit ranging from 1 to N and N being an integer larger than 1; (c) iteratively calculating fractal surface areas Aj""s based on the bit function B(i), wherein j is an integer ranging from 1 to M and M is an integer larger than 1; (d) determining an intermediate parameter I by using the fractal surface areas Aj""s; (e) evaluating a Hurst parameter H based on the fractal surface areas; (f) allocating a bandwidth to the bit streams based on the Hurst parameter H; and (g) transmitting the bit streams to the ATM network based on the allocated bandwidth.
In accordance with another aspect of the present invention, there is provided an apparatus for allocating a bandwidth to bit streams of a video signal having variable bit rates, wherein the bit streams are transmitted to an ATM network, comprising: means for encoding the video signal to thereby generate the bit streams of the encoded video signal; means for generating a bit function B(i) of the bit streams, wherein the bit function represents the amount of bits per predetermined ith unit in the bit streams, i being an index of the predetermined unit ranging from 1 to N and N being an integer larger than 1; means for iteratively calculating fractal surface areas Aj""s based on the bit function B(i), wherein j is an integer ranging from 1 to M and M is an integer larger than 1; means for determining an intermediate parameter I by using the fractal surface areas Aj""s; means for evaluating a Hurst parameter H based on the fractal surface areas; means for allocating a bandwidth to the bit streams based on the Hurst parameter H; means for storing the bit streams; and means for transmitting the stored bit streams to the ATM network based on the allocated bandwidth.